#include <bits/stdc++.h>

using namespace std;

// 在二叉树中分配硬币
// 给你一个有 n 个结点的二叉树的根结点 root
// 其中树中每个结点 node 都对应有 node.val 枚硬币
// 整棵树上一共有 n 枚硬币
// 在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点
// 移动可以是从父结点到子结点，或者从子结点移动到父结点
// 返回使每个结点上 只有 一枚硬币所需的 最少 移动次数
// 测试链接 : https://leetcode.cn/problems/distribute-coins-in-binary-tree/

// 不需要提交这个类
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution 
{
private:
    struct Info
    {
        int cnt, sum, move;
        Info(int a, int b, int c)
        {
            cnt = a; // 子树的节点个数
            sum = b; // 子树的硬币总和
            move = c; // 子树中的硬币的最少移动次数
        }
    };

    Info f(TreeNode* x)
    {
        if(x == nullptr) return Info(0, 0, 0);
        Info infol = f(x->left);
        Info infor = f(x->right);
        int cnt = infol.cnt + infor.cnt + 1; // 子树 x 的节点总数
        int sum = infol.sum + infor.sum + x->val; // 子树 x 的硬币总数
        // abs(infol.cnt - infol.sum) ： 父节点 x 要想左子树分配的硬币个数
        // abs(infor.cnt - infor.sum) ： 父节点 x 要想右子树分配的硬币个数
        int move = infol.move + infor.move + abs(infol.cnt - infol.sum) + abs(infor.cnt - infor.sum);
        return Info(cnt, sum, move);
    }

public:
    int distributeCoins(TreeNode* root) 
    {
        return f(root).move;
    }
};